package com.peng.sort.quick;

import java.util.Arrays;

/**
 *  quick sort 01 : partition  2 part ( <= pivot  and  > pivot )
 */
public class QuickSort01 {

    /*

    i=0,i++ i<n
    j=i,j<n

    i=n-1,i--,i>0
    j=0,j<i;j++


     */
    public static void main(String[] args) {
        int[] arr = {3,5,1,2,3,7,9};
        quickSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr) {
        process(arr,0,arr.length-1);
    }

    private static void process(int[] arr, int L, int R) {
        if(L>=R){
            return;
        }
        int pivot = getPivot(arr,L,R);

        process(arr,L,pivot-1);
        process(arr,pivot+1,R);


    }

    private static int getPivot(int[] arr, int L, int R) {

        if(L>R){
            return -1;
        }
        if(L==R){
            return L;
        }

        int lessAndEq = L-1;
        int i = L;

        while (i<R){
            if(arr[i]<=arr[R]){
                swap(arr,i,++lessAndEq);
            }
            i++;
        }

        swap(arr,++lessAndEq,R);


        return  lessAndEq;
    }

    private static void swap(int[] arr, int i, int j) {
        if(i==j)return;
        int temp = arr[i];
        arr[i] =arr[j];
        arr[j] = temp;
    }
}
